package daily.year2024.m11;

/**
 * No31.下一个排列
 *
 * @author wjs 2024/11/4
 */
public class d4 {
    //思路：从最后一个下标开始遍历，找处于当前元素后面的 大于当前元素的最小值
    //找到之后，交换两个元素，从当前下标加一往后进行排序
    class Solution1 {
        public void nextPermutation(int[] nums) {
            int n = nums.length;
            boolean modify = false;
            for(int i=n-2;i >= 0 && !modify;i--) {
                int val = 1000, idx = 0;
                for(int j=i+1;j < n;j++) {
                    if(nums[j] > nums[i] && nums[j] < val) {
                        val = nums[j];
                        idx = j;
                        modify = true;
                    }
                }
                if(modify) {
                    changeNums(nums,i,idx);
                    sort(nums,i+1);
                }
            }
            if(!modify) {
                //重新排序
                int l = 0, r = n-1;
                for(;l < r;) {
                    changeNums(nums,l,r);
                    l++;
                    r--;
                }
            }
        }

        private void sort(int[] nums, int start) {
            int end = nums.length-1;
            for(;start < end;end--) {
                int max = 0, maxIdx = -1;
                for(int i=start;i <= end;i++) {
                    if(nums[i] > max) {
                        max = nums[i];
                        maxIdx = i;
                    }
                }
                if(maxIdx != -1) {
                    nums[maxIdx] = nums[end];
                    nums[end] = max;
                }
            }
        }

        private void changeNums(int[] nums, int i, int j) {
            int temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
        }
    }

    //改进解法，时间复杂度O(n)
    class Solution2 {
        public void nextPermutation(int[] nums) {
            boolean flag = false;
            for(int i=nums.length-2;i >= 0 && !flag;i--) {
                if(nums[i] < nums[i+1]) {
                    flag = true;
                    int min = nums[i+1], idx = i+1;
                    for(int j=i+2;j < nums.length;j++) {
                        //这里判断用<=是为了方便处理后续的交换环节
                        if(nums[j] <= min && nums[j] > nums[i]) {
                            min = nums[j];
                            idx = j;
                        }
                    }
                    swap(nums,i,idx);
                    reverse(nums,i+1,nums.length-1);
                }
            }
            if(!flag) {
                reverse(nums,0,nums.length-1);
            }
        }

        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }

        private void reverse(int[] nums, int start, int end) {
            for(;start < end;) {
                swap(nums,start,end);
                start++;
                end--;
            }
        }
    }
}
